This application relates generally to processing systems, and, more particularly, to allocation of store queue entries in processing systems.
Processing systems utilize two basic memory access instructions: a store instruction that writes information from a register to a memory location and a load instruction that reads information out of a memory location and loads the information into a register. High-performance out-of-order execution microprocessors can execute load and store instructions out of program order. For example, a program code may include a series of memory access instructions including load instructions (L1, L2, . . . ) and store instructions (S1, S2, . . . ) that are to be executed in the order: S1, L1, S2, L2, . . . However, the out-of-order processor may select the instructions in a different order such as L1, L2, S1, S2, . . . Some instruction set architectures (e.g. the x86 instruction set architecture) require strong ordering of memory operations. Generally, memory operations are strongly ordered if they appear to have occurred in the program order specified. When attempting to execute instructions out of order, the processor must respect true dependencies between instructions because executing load instructions and store instructions out of order can produce incorrect results if a dependent load/store pair was executed out of order. For example, if (older) S1 stores data to the same physical address that (younger) L1 subsequently reads data from, the store S1 must be completed (or retired) before L1 is performed so that the correct data is stored at the physical address for L1 to read.
Store and load instructions typically operate on memory locations in one or more caches associated with the processor. Values from store instructions are not committed to the memory system (e.g., the caches) immediately after execution of the store instruction. Instead, the store instructions, including the memory address and store data, are buffered in a store queue so they can be written in-order. Eventually, the store commits and the buffered data is written to the memory system. Buffering store instructions can be used to help reorder store instructions so that they can commit in order. However, buffering store instructions can introduce other complications. For example, a load instruction can read an old, out-of-date value from a memory address if a store instruction executes and buffers data for the same memory address in the store queue and the load attempts to read the memory value before the store instruction has retired.
A technique called store-to-load forwarding can provide data directly from the store queue to a requesting load. For example, the store queue can forward data from completed but not-yet-committed (“in-flight”) store instructions to later (younger) load instructions. The store queue in this case functions as a Content-Addressable Memory (CAM) that can be searched using the memory address instead of a simple FIFO queue. When store-to-load forwarding is implemented, each load instruction searches the store queue for in-flight store instructions to the same address. The load instruction can obtain the requested data value from a matching store instruction that is logically earlier in program order (i.e. older). If there is no matching store instruction, the load instruction can access the memory system to obtain the requested value as long as any preceding matching store instructions have been retired and have committed their values to the memory.